/**
 * @Author YuanYuan
 * @Date 2022/5/9
 * @Time 10:11
 */
public class TestDemo {
    /**
     * KMP算法实现
     * 1. 先实现next数据生成
     * 2. 然后根据next数据进行匹配
     */
    public static int[] getNext(String s){
        int[] next = new int[s.length()];
        next[0] = -1;
        next[1] = 0;
        int j = 2;
        int k = -1;
        while(j < s.length() ){
            if(k == -1 || s.charAt(j-1) == s.charAt(k)){
                    next[j] = k+1;
                    k++;
            }else{
                k = next[k];
            }
            j++;
        }
        return next;
    }
    // s1 is main string ,s2 is pattern string
    public static int KMP(String s1, String s2){
        // the index of s1
        int i = 0;
        // the index of s2
        int j = 0;
        int[] next = getNext(s2);
        while (i < s1.length() && j < s2.length()){
            if(j == -1 || s1.charAt(i) == s2.charAt(j)){
                i ++;
                j ++;
            }else{
                // 与暴力的不同
                j = next[j];
            }
        }
        return j == s2.length() ? i - j : -1;
    }
    public static void main(String[] args) {
        String arr1 = "001234124567";
        String arr2 = "12341245";
        String arr3 = "078";
        String arr4 = "abcababcabdd";
        String arr5 = "abcababcabc";
        //System.out.println(myKMP(arr1,arr2));
        System.out.println(KMP(arr4,arr5));
    }

}
